1. Field of the Invention
The present invention relates generally to coordination amongst execution sequences in a multiprocessor computer, and more particularly, to structures and techniques for facilitating non-blocking implementations of dynamically sizable shared data structures.
2. Description of the Related Art
Most existing nonblocking algorithms (including lock-free and wait-free algorithms) require a priori knowledge of N, the number of processes (or threads) that will potentially participate. Many such algorithms also have space consumption and/or time complexity that depend on N, and will behave incorrectly if N is underestimated. In practice, this dependence results in overly conservative estimates of N and, as a result, in wasted time and space. Some researchers have addressed the time complexity part of this problem by designing algorithms whose time complexity “adapts” to the number of processes that actually participate. See e.g., M. Moir and J. Anderson, Wait-Free Algorithms for Fast, Long-Lived Renaming, Science of Computer Programming, 25:1-39 (1995); Y. Afek, D. Dauber, and D. Touitou, Wait-free Made Fast, In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 538-547 (1995); and Y. Afek, H. Attiya, A. Fouren, G. Stupp, and D. Touitou, Long-lived Renaming Made Adaptive, In Proceedings of the 18th Annual ACM Symposium on Principles of Distributed Computing, pp. 91-104 (1999).
As discussed in more detail later, most of these research efforts have been based on the assumption that only read and write operations are available, which is not true in modern shared-memory multiprocessors. This restriction has led to algorithms that are ingenious and beautiful—but ultimately impractical. It has, in our view, also prevented the work from addressing either the space overhead problem or the need for a known bound on the number of processes that potentially participate.
Other results (see e.g., M. Michael and M. Scott, Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms, In Proceedings of the 15th Annual ACM Symposium on the Principles of Distributed Computing, pp. 267-276 (1996)) do not require knowledge of N, and can allocate space dynamically as required, but cannot reclaim space after it has been used. To our knowledge, the only algorithm that does not exhibit the aforementioned shortcomings is Treiber's link-list-based set data structure. See R. Treiber, Systems Programming: Coping with Parallelism, Technical Report RJ5118, IBM Almaden Research Center (1986). Unfortunately, Treiber's techniques can be prevented from future memory reclamation by a single process failure.
What is needed is structures and techniques that facilitate the design of nonblocking algorithms that do not require advance knowledge of the number of processes that participate, whose time complexity and space consumption are both adaptive and which are not prevented from future memory reclamation should a single process (or thread) fail.